(define (*2x2 x y)
  (let ((z00 (+ (* (vector-ref x 0) (vector-ref y 0))
                (* (vector-ref x 1) (vector-ref y 2))))
        (z01 (+ (* (vector-ref x 0) (vector-ref y 1))
                (* (vector-ref x 1) (vector-ref y 3))))
        (z10 (+ (* (vector-ref x 2) (vector-ref y 0))
                (* (vector-ref x 3) (vector-ref y 2))))
        (z11 (+ (* (vector-ref x 2) (vector-ref y 1))
                (* (vector-ref x 3) (vector-ref y 3)))))
    (vector z00 z01 z10 z11)))

(define base (vector 1 1 1 0))

;; slow
;; (define (pow2x2 f n) (pow2x2* f 2 n))
;; (define (pow2x2* f i n)
;;   (if (<= i n)
;;       (pow2x2* (*2x2 f base) (+ i 1) n)
;;       f))

;; binary exponentiation
(define (pow2x2 f n)
  (cond ((= n 0) f)
        ((= n 1) f)
        (else
         (let* ((f1 (pow2x2 f (floor (/ n 2))))
                (f2 (*2x2 f1 f1)))
           (if (odd? n)
               (*2x2 f2 base)
               f2)))))


(define (fib n)
  (if (= n 0)
      0
      (vector-ref (pow2x2 base (- n 1)) 0)))
